package practice1_100;

import java.util.*;

public class Cubao  {
    public List<String> findWords(char[][] board, String[] words) {
        Set<Character> set=new HashSet<>();
        for(int i=0;i<words.length;i++){
            set.add(words[i].charAt(0));
        }
        Set<String> res=new HashSet<>();
        //set中存在的就从这里开始
        for(int i=0;i<board.length;i++){
            for(int j=0;j<board[0].length;j++){
                if(set.contains(board[i][j])){
                    //从这里开始搜索
                    boolean[][] vis=new boolean[board.length][board[0].length];
                    StringBuffer strBuf=new StringBuffer();
                    search( board, words,  res, i, j,strBuf,vis);
                }
            }
        }
        //排除所有的
        List<String> result=new LinkedList<>();
        for(int i=0;i<words.length;i++){
            if(res.contains(words[i])){
                result.add(words[i]);
            }
        }
        return result;
    }
    public void search(char[][] board,String[] words, Set<String> res,int i,int j,StringBuffer strBuf,boolean[][] vis){
        if(i>=board.length||j>=board[0].length||i<0||j<0)return;
        if(vis[i][j]==true)return;

        strBuf.append(board[i][j]);
        vis[i][j]=true;
        res.add(strBuf.toString());
        search(board,words,res,i-1,j,strBuf,vis);
        search(board,words,res,i+1,j,strBuf,vis);
        search(board,words,res,i,j-1,strBuf,vis);
        search(board,words,res,i,j+1,strBuf,vis);
        strBuf.deleteCharAt(strBuf.length()-1);
        vis[i][j]=false;

    }

    public static void main(String[] args) {
        //[["o","a","a","n"],["e","t","a","e"],["i","h","k","r"],["i","f","l","v"]]
        //["oath","pea","eat","rain"]
//        [["a","a"]]
//        ["aa"]
        //new Cubao().findWords(new char[][]{{'o','a','a','n'},{'e','t','a','e'},{'i','h','k','r'},{'i','f','l','v'}},new String[]{"oath","pea","eat","rain"});
        //new Cubao().findWords(new char[][]{{'a','a'}},new String[]{"aa"});
       char[][] temp= new char[][]{{'a','a','a','a','a','a','a','a','a','a','a','a'},{'a','a','a','a','a','a','a','a','a','a','a','a'},{'a','a','a','a','a','a','a','a','a','a','a','a'},{'a','a','a','a','a','a','a','a','a','a','a','a'},{'a','a','a','a','a','a','a','a','a','a','a','a'},{'a','a','a','a','a','a','a','a','a','a','a','a'},{'a','a','a','a','a','a','a','a','a','a','a','a'},{'a','a','a','a','a','a','a','a','a','a','a','a'},{'a','a','a','a','a','a','a','a','a','a','a','a'},{'a','a','a','a','a','a','a','a','a','a','a','a'},{'a','a','a','a','a','a','a','a','a','a','a','a'},{'a','a','a','a','a','a','a','a','a','a','a','a'}};
        new Cubao().findWords(temp,new String[]{"a","aa","aaa","aaaa","aaaaa","aaaaaa","aaaaaaa","aaaaaaaa","aaaaaaaaa","aaaaaaaaaa"});
    }
}
